package main

import "fmt"

//给定一个二维的矩阵，包含 'X' 和 'O'（字母 O）。
//
//找到所有被 'X' 围绕的区域，并将这些区域里所有的 'O' 用 'X' 填充。
//
//示例:
//
//X X X X
//X O O X
//X X O X
//X O X X
//运行你的函数后，矩阵变为：
//
//X X X X
//X X X X
//X X X X
//X O X X
//解释:
//
//被围绕的区间不会存在于边界上，换句话说，任何边界上的 'O' 都不会被填充为 'X'。 任何不在边界上，或不与边界上的 'O' 相连的 'O' 最终都会被填充为 'X'。如果两个元素在水平或垂直方向相邻，则称它们是“相连”的。
//
//
//
//这道题目是经典的染色问题，由题意可以分析出来，只有边界上与O相连的点不会被吃，
// 内部其他点都被会染为X。所以思路是四个边界开始染色，先染成一个其他颜色，
// '#'，然后再全部遍历一遍处理

func dfs(board [][]uint8, x int, y int){
	if x < 0 || x >= len(board) || y < 0 || y  >= len(board[0]) || board[x][y] == 'X' ||
		board[x][y] == '#'{
		return
	}

	board[x][y] = '#'
	dfs(board, x-1, y)
	dfs(board, x+1, y)

	dfs(board, x, y-1)
	dfs(board, x, y+1)
}

func slove(board [][]uint8){
	r, c := len(board), len(board[0])
	for i := 0; i < r ; i++{
		if board[i][0] == 'O'{
			dfs(board, i, 0)
		}
		if board[i][c-1] == 'O' {
			dfs(board, i, c-1)
		}
	}

	for j := 0; j < c; j++{
		if board[0][j] == 'O'{
			dfs(board, 0, j)
		}
		if board[r-1][j] == '0'{
			dfs(board, r-1, j)
		}
	}

	for i := 0; i < r; i++{
		for j := 0; j < c; j++{
			if board[i][j] == '#'{
				board[i][j] = '0'
			}else{
				board[i][j] = 'X'
			}
		}
	}
}

func main(){
	board := make([][]uint8, 4)
	board[0] = []uint8{'X', 'X',  'X', 'X'}
	board[1] = []uint8{'X', '0',  '0', 'X'}
	board[2] = []uint8{'X', 'X',  '0', 'X'}
	board[3] = []uint8{'X', '0',  'X', 'X'}
	slove(board)
	fmt.Println(board)
}
